﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.Algorithm.Sort
{
    class MergeSort<T> : AbstractSort<T>
        where T : IComparable
    {
        public override void Sort(T[] list)
        {
            int count = list.Length;
            T[] aux = (T[])list.Clone();
            Sort(list, aux, 0, count-1);
        }

        private void Sort(T[] list, T[] aux, int low, int high)
        {
            if (low < high)
            {
                int mid = low + (high - low) / 2;
                Sort(aux, list, low, mid);
                Sort(aux, list, mid + 1, high);
                Merge(aux, list, low, high, mid);
            }            
        }

        private void Merge(T[] list, T[] aux, int low, int high, int mid)
        {            
            int i = low, j = mid +1;
            for (int k = low; k <= high; k++)
            {
                if (i > mid)
                    aux[k] = list[j++];
                else if (j > high)
                    aux[k] = list[i++];
                else if (IsLess(aux[i], aux[j]))
                    aux[k] = list[i++];
                else
                    aux[k] = list[j++];                    
            }           
           
        }
    }
}
